package 链表;

import java.util.ArrayList;

public class Solution8 {
    //https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
    //思路：使用集合装节点，定义节点的大小比较规则后，进行排序再取出
    public ListNode sortInList (ListNode head) {
        ArrayList<ListNode> arrayList = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            arrayList.add(cur);
            cur = cur.next;
        }
        arrayList.sort((node1,node2) -> node1.val - node2.val);

        ListNode reHead = arrayList.get(0);
        for (int i = 0; i < arrayList.size() - 1; i++) {
            arrayList.get(i).next = arrayList.get(i + 1);
        }
        //最后一个节点的next要置为空
        arrayList.get(arrayList.size() - 1).next = null;
        return reHead;

//        ListNode reHead = null;
//        for (int i = 0; i < arrayList.size()/* - 1*/; i++) {
//            if(i == arrayList.size() - 1) {
//                arrayList.get(i).next = null;
//                break;
//            }
//            if(i == 0) {
//               reHead = arrayList.get(i);
//            }
//            arrayList.get(i).next = arrayList.get(i + 1);
//            //最后一个节点的next要置为空
//        }
//        return reHead;
    }
}
